# 登山(好题, 并查集)
# 2025/5/25

"""
小蓝正在登山，山峰的高度构成 n 行 m 列的正整数矩阵，ai, j 表示第 i 行 第 j 列格子 (i, j) 上的山峰的高度。小蓝以一种特别的方式进行登山，
如果他此刻在第 p 行第 q 列的格子 (p, q) 上，那么下一步可以选择：

1) 走到格子 (i, q)，满足 a_{i,q} < a_{p,q} 且 i > p ； 向下只能下山

2) 走到格子 (i, q)，满足 a_{i,q} > a_{p,q} 且 i < p ； 向上只能上山

3) 走到格子 (p, j)，满足 a_{p, j} < a_{p,q} 且 j > q ；向右只能下山

4) 走到格子 (p, j)，满足 a_{p, j} > a_{p,q} 且 j < q 。向左只能上山

小蓝想知道，如果他依次从每一个格子开始出发，按照最优策略，他最高 能到达的山峰的高度的平均值是多少？

输入格式:
输入的第一行包含两个正整数 n, m ，用一个空格分隔。
接下来 n 行，每行包含 m 个正整数。其中第 i 行包含 ai,1, ai,2, · · · , ai,m ，相 邻整数之间使用一个空格分隔。
2 2
1 3
3 2

输出格式:
输出一行包含一个实数表示答案，四舍五入保留正好 6 位小数。
2.500000

四舍五入保留6位小数的方法:
1. 使用format函数:
format(math.sqrt(s / n), '.6f')

2.另一种形式的format函数:
"{:.2f}".format(tsp_dp(cost))

直接截取6为小数的方法:
int(num * 1000000) / 1000000
"""


def avg_height(n: int, m: int, matrix: list[list[int]]) -> str:
    """
    通过率: 3/20, 其余为超时或者递归超过限制
    """
    total_node = m * n
    records = []
    max_height = max(max(nums) for nums in matrix)  # 矩阵中的最大高度
    mapping = {}  # 记录缓存

    def dfs(path, curr):
        nonlocal record, max_height, total_node, mapping  # 当前起点的达到的最大高度, 矩阵中的最大高度
        path.add(curr)
        x, y = curr[0], curr[1]
        curr_h = matrix[x][y]
        record = max(record, curr_h)
        if curr in mapping.keys():  # 如果当前节点此前已经记录过, 那么直接从mapping中调取即可
            record = max(record, mapping.get(curr))
            return
        if record == max_height:  # 已经达到最大高度
            return
        if len(path) == total_node:  # 已经遍历全部节点
            return

        # 纵向移动
        for i in range(n):
            nxt = (i, y)
            if nxt in path or (i < x and matrix[i][y] < curr_h) or (i > x and matrix[i][y] > curr_h):
                continue
            dfs(path, nxt)
            path.remove(nxt)
        # 横向移动
        for i in range(m):
            nxt = (x, i)
            if nxt in path or (i < y and matrix[x][i] < curr_h) or (i > y and matrix[x][i] > curr_h):
                continue
            dfs(path, nxt)
            path.remove(nxt)

    for i in range(n):
        for j in range(m):
            record = 0
            dfs(set(), (i, j))
            mapping[(i, j)] = record  # 将当前节点的记录添加进mapping中
            records.append(record)
    res = sum(records) / len(records)
    return "{:.6f}".format(res)


def avg_height_opt(n: int, m: int, matrix: list[list[int]]) -> str:
    """
    我们可以将 n×m 个元素抽象成一张图 G。题目给出的四种选择即构成了 G 中的边。

    注意到选择 1 和选择 2、选择 3 和选择 4 是对称的，即如果 a 能直接走到 b，那么 b 就能直接走到 a，因而这些边是双向的。
    只要我们使用并查集求出哪些节点是互相可达的，以及每个连通块里高度最高的节点，即可快速求解。

    考虑同一列的格子之间的直接连边，同一行的格子的情况类似。假设第 i 列格子自上而下的高度分别为 h1, h2 ... hm,
    那么任意两个高度 hx 和 hy, 仅在 hx > hy 时 可以连边。换言之，只要存在一个逆序对，就有一对双向边！

    那么可以直接给出命题:
    对于第 j 列，设 pre[i] 表示前 i 个元素的最大值，suf[i] 表示 [i,n] 内元素的最小值，如果 pre[i]>suf[i+1]，
    就连一条 (i,j) 到 (i+1,j) 的边。

    为了方便，做几点说明:
    1. 逆序对连边生成的边集为 E0，相邻连边生成的边集为 E1.
    2. 简写 (l,j) 到 (r,j) 连双向边为 l⟺r。
    """

    class DSU:
        def __init__(self, size: int):
            self.parent = list(range(size))  # 初始状态下每个元素的父节点都指向其自身
            self.rank = [1] * size

        def find(self, x):
            """find操作:查询元素属于哪个集合(查找根节点)"""
            while self.parent[x] != x:
                self.parent[x] = self.parent[self.parent[x]]  # 路径压缩: 相同根节点的元素的父节点均直接指向其根节点, 降低树的高度
                x = self.parent[x]
            return x

        def union(self, x, y):
            """find操作:查询元素属于哪个集合(查找根节点)"""
            root_x = self.find(x)
            root_y = self.find(y)
            # 按秩合并: 按照树的大小合并(另一个选择是按照树的深度合并)
            if root_x != root_y:
                if self.rank[root_x] < self.rank[root_y]:
                    root_x, root_y = root_y, root_x
                self.parent[root_y] = root_x
                self.rank[root_x] += self.rank[root_y]

        def size(self, idx):
            return self.rank[self.find(idx)]


    N = n * m
    dsu = DSU(N)
    inf = float('inf')

    # 使用并查集合并每一行
    for i in range(n):
        pre = [0] * (m + 1)
        suf = [inf] * (m + 1)
        for j in range(m):
            pre[j + 1] = max(pre[j], matrix[i][j])
        for j in range(m - 1, -1, -1):
            suf[j] = min(suf[j + 1], matrix[i][j])
        for j in range(1, m):
            if pre[j] > suf[j]:
                dsu.union(i * m + j - 1, i * m + j)

    # 使用并查集合并每一列
    for j in range(m):
        pre = [0] * (n + 1)
        suf = [inf] * (n + 1)
        for i in range(n):
            pre[i + 1] = max(pre[i], matrix[i][j])
        for i in range(n - 1, -1, -1):
            suf[i] = min(suf[i + 1], matrix[i][j])
        for i in range(1, n):
            if pre[i] > suf[i]:
                dsu.union((i - 1) * m + j, i * m + j)

    # 统计每个组件的最大值
    comp_max = [0] * N
    for i in range(n):
        for j in range(m):
            idx = i * m + j
            r = dsu.find(idx)
            comp_max[r] = max(comp_max[r], matrix[i][j])

    # 求和并计算平均
    total = 0
    for idx in range(N):
        if dsu.find(idx) == idx:
            total += dsu.size(idx) * comp_max[idx]

    # Return average
    return "{:.6f}".format(total / (n * m))


if __name__ == '__main__':
    n, m = map(int, input().split())
    matrx = []
    for _ in range(n):
        matrx.append(list(map(int, input().split())))
    print(avg_height(n, m, matrx))
    print(avg_height_opt(n, m, matrx))
"""
输入:
2 2
1 3
3 2
输出: 2.500000
输入:
2 3 
2 4 1 
4 2 5 
records = [2, ]
输出: 4.166667 
"""
